package week07

// 10. 正则表达式匹配
// https://leetcode-cn.com/problems/regular-expression-matching/

func isMatch(s string, p string) bool {
	var m, n = len(s), len(p)
	s, p = " " + s, " " + p
	var dp = make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	// _* 和 "" 是匹配的
	for i := 2; i <= n && p[i] == '*'; i+=2 {
		dp[0][i] = true
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j] == '*' {
				// _* 和 s[i] 匹配
				dp[i][j] = dp[i][j-2]   // _* 和 0 个字符匹配
				if p[j-1] == '.' || p[j-1] == s[i] {
					// s[0 ~ i-1] 和 p[0 ~ j] 能匹配上
					dp[i][j] = dp[i-1][j] || dp[i][j]
				}
			} else if p[j] == '.' {
				dp[i][j] = dp[i-1][j-1]
			} else {    // 字符
				dp[i][j] = dp[i-1][j-1] && s[i] == p[j]
			}
		}
	}
	return dp[m][n]
}